跳到主要内容

剑指 Offer II 060.出现频率最高的 k 个数字

· 阅读需 3 分钟

1、题干​

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

 

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字


3、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 空间复杂度：O(n)O(n)

5、解法2-桶排序​

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入按数量存入桶中，最后返回前 k 个数字。其时间复杂度为 O(n)O(n)，解决了进阶问题。


6、代码​

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)